#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int N=200020;
const int MOD=10007;
int Next[N];
char s[N];
int dp[N];
int t,n;
void kmp_pre(char* s){
    int i=0;
    int j=-1;
    Next[0]=-1;
    while(i<n){
        if(j==-1 || s[i]==s[j]){
            i++;
            j++;
            Next[i]=j;
        }
        else{
            j=Next[j];
        }
    }
}
int main(void){
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        scanf("%s",s);
        memset(Next,0,sizeof(Next));
        memset(dp,0,sizeof(dp));
        kmp_pre(s);
        int ans=0;
        for(int i=0;i<=n;i++){
            printf("%d ",Next[i]);
        }
        printf("\n");
        for(int i=1;i<=n;i++){
            dp[i]=(dp[Next[i]]+1)%MOD;
            //printf("%d\n",dp[i]);
            ans=(ans+dp[i])%MOD;
        }
        printf("%d\n",ans);
    }
    return 0;
}
